package com.my.test.string;


/**
 * A programming test from codility. Need time complexity O(n), space complexity O(1)
 *
 * @author Wormholes
 *
 */
public class ArrayMidSplit {
	
	/**
	 * An array like: {5,5,1,2,3,7,5}, will be split to {5,5,1}, {3,7,5}. For {5,5,1} match count is 2, for {3,7,5} unmatch count 
	 * is 2 also, so d[3] is the split point.
	 * 
	 * @param x
	 * @param a
	 * @return The split index, -1 if no split point can be found.
	 */
	public static int splitMidArray(int x, int[] a) {
		int matchCnt = 0;
		int notMatchCnt = 0;
		int i = 0;
		int j = a.length;
		if(a.length < 3) return -1;
		//{5,5,1,2,3,7,5}
		while (i < j-1) {
			// if a[i] != x, loop to find a match and remember the match count
			while (i < j - 1 && a[i] != x) {
				i++;
			}
			if (i < j - 1 && a[i] == x) {
				matchCnt++;
				j--;
			}
			// if a match found, turn to find a notMatch. If a[j] == x, loop to
			// find a not match and remember the not match count
			while (i < j - 1 && a[j] == x) {
				j--;
			}
			if (i < j - 1 && a[j] != x) {
				notMatchCnt++;
				i++;
			}

		}
		if(matchCnt != notMatchCnt) {
			return -1;
		} else {
			return i; 
		}
		
	}

	public static void main(String[] args) {
		System.out.println(splitMidArray(5, new int[] {5,5,1,2,3,7,5}));
		System.out.println(splitMidArray(5, new int[] {4,5,5,5,3,5,0}));
		System.out.println(splitMidArray(5, new int[] {4,5,5,3,6,0}));
		System.out.println(splitMidArray(5, new int[] {1,2,3,5,7}));
		System.out.println(splitMidArray(5, new int[] {1,5,3,6}));
		System.out.println(splitMidArray(5, new int[] {5,5,2,3,4,6,7}));
		System.out.println(splitMidArray(5, new int[] {5}));
		System.out.println(splitMidArray(5, new int[] {5,2,1}));
		System.out.println(splitMidArray(5, new int[] {5,6,3,5,5,5,2,1}));
	}

}
